package general_tips;

import java.util.Arrays;

public class CountPrimes {
    public static void main(String[] args) {
        CountPrimes c = new CountPrimes();
        System.out.println( c.countPrime(100));
        System.out.println( c.countPrime1(100));
        System.out.println( c.countPrime2(100));

    }

    /**
     * 原始方法，先定义一个函数判断是否是素数，然后再循环统计
     * @param n
     * @return
     */
    public int countPrime(int n){

        int count=0;
        for(int i=0;i<=n;i++){
            if(isPrime(i)) count++;
        }
        return count;
    }

    /**
     * 利用排除法的思想，判断[2,n]有几个素数
     * @param n
     * @return
     */
    public int countPrime1(int n){
        //初始化一个布尔类型的数组，将其都设置为true;
        //循环遍历，将2的整数被都设置为false
        //最后计数
        boolean flag[]=new boolean[n+1];
        Arrays.fill(flag,true);
        for(int i=2;i<n+1;i++){
            if(flag[i]){
                for(int j=2*i;j<n+1;j+=i){
                    flag[j]=false;
                }
            }
        }
        int count=0;
        for(int i=2;i<n+1;i++){
            if(flag[i]) count++;
        }

        return count;
    }
    public int countPrime2(int n){

        boolean flag[]=new boolean[n+1];
        Arrays.fill(flag,true);
        for(int i=2;i*i<n+1;i++){
            if(flag[i]){
                //前面的有些数已经置为false了，不需要重复
                for(int j=i*i;j<n+1;j+=i){
                    flag[j]=false;
                }
            }
        }
        int count=0;
        for(int i=2;i<n+1;i++){
            if(flag[i]) count++;
        }
        return count;
    }
    public boolean isPrime(int n){
        if(n<=1) return false;
        for(int i=2;i<n;i++){
            if(n%i==0) return false;
        }
        return true;
    }
    public boolean isPrime2(int n){
        //比如n=12只需要判断它能否被[2,sqrt(n))之间的数整除，因为前后是对称的
        if(n<=1) return false;
        for(int i=2;i*i<n;i++){
            if(n%i==0) return false;
        }
        return true;
    }
}
